import java.util.*;

/**
 * @author LKQ
 * @date 2022/7/1 9:23
 * @description 备忘录 + 分治
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> list = solution.diffWaysToCompute("2*3-4*5");
        System.out.println(list.toString());
    }

    /**
     * 记录已经计算出来的字符串对应的值，避免重复计算
     */
    private static final Map<String, List<Integer>> map = new HashMap<>();

    public List<Integer> diffWaysToCompute(String input) {
        if (map.containsKey(input)) {
            return map.get(input);
        }
        List<Integer> list = new ArrayList<>();
        int len = input.length();
        for (int i = 0; i < len; i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                //出现运算符号，递归运算求解前半段和后半段
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));
                for (int a: left) {
                    for (int b: right) {
                        switch (c) {
                            case '+':
                                list.add(a + b);
                                break;
                            case '-':
                                list.add(a - b);
                                break;
                            case '*':
                                list.add(a * b);
                                break;
                            default:
                                break;
                        }
                    }
                }
            }
        }
        // 单独一个数字时，将字符串转换为整数
        if (list.size() == 0) {
            list.add(Integer.valueOf(input));
        }
        map.put(input, list);
        return list;
    }
}
